#include <stdio.h>
#include <stdlib.h>
#include "reverse.h"


//初始化一个没有头节点的链表
link *initLink() {
    //头指针
    link *p = NULL;
    //首元节点
    link *temp = (link *) malloc(sizeof(link));
    //首元节点初始化
    temp->data = 1;
    temp->next = NULL;
    //头指针指向首元节点
    p = temp;
    for (int i = 2; i < 5; ++i) {
        //创建一个新的节点并初始化
        link *a = (link *) malloc(sizeof(link));
        a->data = i;
        a->next = NULL;
        //将temp节点和新节点建立关联关系
        temp->next = a;
        //把首元节点的指针指向新的链表的最后一个节点
        temp = temp->next;
    }

    return p;
}

//创建一个拥有头节点的链表
link *initLinkWithHeadNode() {
    //创建一个头节点
    link *p = (link *) malloc(sizeof(link));
    //声明一个指针指向头结点
    link *temp = p;
    for (int i = 1; i < 5; ++i) {
        link *a = (link *) malloc(sizeof(link));
        a->data = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }

    //返回头节点
    return p;
}

//打印没有头节点的链表
void displayLink(link *p) {
    link *temp = p;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    printf("\n");
}

//打印有头节点的链表
void displayLinkWithHeadNode(link *p) {
    link *temp = p;
    while (temp->next) {
        temp = temp->next;
        printf("%d ", temp->data);
    }

    printf("\n");
}

//为链表插入一个元素
//link* p 是原链表的指针
//int location 是插入位置
//int data 是插入的数据
link *insertElem(link *p, int location, int data) {
    //1.将新元素的next指向插入位置后的元素
    //2. 将插入元素前的节点指向新节点

    link *temp = p;
    link *new = NULL;
    //找出新元素前的节点
    for (int i = 1; i < location; i++) {
        if (temp->next == NULL) {
            printf("插入位置无效");
            return p;
        }
        temp = temp->next;
    }

    //创建一个新节点
    new = (link *) malloc(sizeof(link));
    new->data = data;
    new->next = NULL;

    //将新节点指向插入后的元素
    new->next = temp->next;

    //将插入元素前的节点指向新节点
    temp->next = new;

    return p;
}

//从链表中删除元素
link *delElem(link *p, int location) {
    //1.找到要删除的位置的上一个节点
    //2. 把这个节点指向删除节点的下一个节点
    //3. 然后把要删除的节点内存释放掉

    //先拿到头结点
    link *temp = p;
    link *del = NULL;
    //找到要删除的节点的上一个节点
    for (int i = 1; i < location; ++i) {
        temp = temp->next;
    }
    //记录要删除的节点地址
    del = temp->next;
    //把上一个节点的指向为删除位置的下一个节点
    temp->next = temp->next->next;

    //释放内存
    free(del);
    return p;
}

//查找位于链表中元素的位置，返回-1表示没有找到数据
int findElem(link *p, int elem) {
    link *temp = p;
    int i = 1;
    while (temp->next) {
        if (temp->next->data == elem) {
            return i;
        }
        temp = temp->next;
        i++;
    }

    //返回-1表示没有找到
    return -1;
}

//更新链表的元素
//link* p 原链表
//int location 要更新的位置
//int data 要更新的值
link *updateElem(link *p, int location, int elem) {
    link *temp = p;
    for (int i = 0; i < location; ++i) {
        temp = temp->next;
    }
    //修改数据
    temp->data = elem;
    return p;
}

void testReverseLink() {
    link *p = NULL;
    printf("初始化链表(无头节点): \n");
    p = initLink();
    displayLink(p);
    printf("执行反转。。。。 \n");
    printf("就地逆置法反转链表 \n");
    p = local_reverse(p);
    displayLink(p);
    printf("头插法反转链表 \n");
    p = initLink();
    p = head_reverse(p);
    displayLink(p);
    printf("迭代反转链表 \n");
    p = initLink();
    p = iteration_reverse(p);
    displayLink(p);
    printf("递归法反转链表 \n");
    p = initLink();
    p = recursive_reverse(p);
    displayLink(p);
}


int main() {
    link *p = NULL;
    printf("初始化链表(有头节点): \n");
    p = initLinkWithHeadNode();
    displayLinkWithHeadNode(p);
    printf("为有头节点插入数据 location:%d data:%d\n", 2, 10);
    p = insertElem(p, 2, 10);
    displayLinkWithHeadNode(p);
    printf("删除上一步location:%d data:%d 插入的节点 \n", 2, 10);
    p = delElem(p, 2);
    displayLinkWithHeadNode(p);
    int needed = 2;
    printf("查找指定的数字节点 needed:%d\n", needed);
    int location = findElem(p, needed);
    printf("要查找的数字是 %d, 找到的位置是 %d \n", needed, location);
    displayLinkWithHeadNode(p);
    printf("替换指定节点的数据,把第三个换成20\n");
    p = updateElem(p, 3, 20);
    displayLinkWithHeadNode(p);

    printf("\n ===============反转链表================= \n");
    testReverseLink();
    return 0;
}


